home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Source Code / Visual Basic Source Code.iso / vbsource / metkit / kboundw.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1997-06-07  |  7.5 KB  |  234 lines
  1. //    Copyright (C) 1996, 1997 Meta Four Software.  All rights reserved.
  2. //
  3. //    See the comments in "kbound.h" for details on how to use this code.
  4. //
  5. //! rev="$Id: kboundw.cpp,v 1.2 1997/05/27 00:06:45 jcw Rel $"
  6.  
  7. #include "kbound.h"
  8.  
  9. /////////////////////////////////////////////////////////////////////////////
  10. //
  11. //    THE LZRW1 ALGORITHM
  12. //    ===================
  13. //    Author : Ross N. Williams.
  14. //    Date   : 31-Mar-1991.
  15. //
  16. //    1. I typed the following code in from my paper "An Extremely Fast Data
  17. //    Compression Algorithm", Data Compression Conference, Utah, 7-11 April,
  18. //    1991. The  fact that this  code works indicates  that the code  in the
  19. //    paper is OK.
  20. //
  21. //    2. This file has been copied into a test harness and works.
  22. //
  23. //    3. Some users running old C compilers may wish to insert blanks around
  24. //    the "="  symbols of  assignments so  as to  avoid expressions  such as
  25. //    "a=*b;" being interpreted as "a=a*b;"
  26. //
  27. //    4. This code is public domain.
  28. //
  29. //    5. Warning:  This code  is non-deterministic insofar  as it  may yield
  30. //    different  compressed representations  of the  same file  on different
  31. //    runs. (However, it will always decompress correctly to the original).
  32. //
  33. //    6. If you use this code in anger (e.g. in a product) drop me a note at
  34. //    ross@spam.ua.oz.au and I will put you  on a mailing list which will be
  35. //    invoked if anyone finds a bug in this code.
  36. //
  37. //    7.   The  internet   newsgroup  comp.compression   might  also   carry
  38. //    information on this algorithm from time to time.
  39. //
  40. /////////////////////////////////////////////////////////////////////////////
  41.  
  42. #define FLAG_BYTES    2     /* Number of bytes used by copy flag. */
  43. #define FLAG_COMPRESS 0     /* Signals that compression occurred. */
  44. #define FLAG_COPY     1     /* Signals that a copyover occurred.  */
  45. static void fast_copy(BYTE *p_src,BYTE *p_dst,int len) /* Fast copy routine. */
  46. {while (len--) *p_dst++=*p_src++;}
  47.  
  48. void lzrw1_compress(BYTE *p_src_first,DWORD src_len,
  49.                     BYTE *p_dst_first,DWORD *p_dst_len)
  50. /* Input  : Specify input block using p_src_first and src_len.          */
  51. /* Input  : Point p_dst_first to the start of the output zone (OZ).     */
  52. /* Input  : Point p_dst_len to a DWORD to receive the output length.    */
  53. /* Input  : Input block and output zone must not overlap.               */
  54. /* Output : Length of output block written to *p_dst_len.               */
  55. /* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. */
  56. /* Output : May write in OZ=Mem[p_dst_first..p_dst_first+src_len+256-1].*/
  57. /* Output : Upon completion guaranteed *p_dst_len<=src_len+FLAG_BYTES.  */
  58. #define PS *p++!=*s++  /* Body of inner unrolled matching loop.         */
  59. #define ITEMMAX 16     /* Maximum number of bytes in an expanded item.  */
  60. {BYTE *p_src=p_src_first,*p_dst=p_dst_first;
  61.  BYTE *p_src_post=p_src_first+src_len,*p_dst_post=p_dst_first+src_len;
  62.  BYTE *p_src_max1=p_src_post-ITEMMAX,*p_src_max16=p_src_post-16*ITEMMAX;
  63.  BYTE *hash[4096],*p_control; WORD control=0,control_bits=0;
  64.  *p_dst=FLAG_COMPRESS; p_dst+=FLAG_BYTES; p_control=p_dst; p_dst+=2;
  65.  while (1)
  66.    {BYTE *p,*s; WORD unroll=16,len,index; DWORD offset;
  67.     if (p_dst>p_dst_post) goto overrun;
  68.     if (p_src>p_src_max16)
  69.       {unroll=1;
  70.        if (p_src>p_src_max1)
  71.          {if (p_src==p_src_post) break; goto literal;}}
  72.     begin_unrolled_loop:
  73.        index=((40543*((((p_src[0]<<4)^p_src[1])<<4)^p_src[2]))>>4) & 0xFFF;
  74.        p=hash[index]; hash[index]=s=p_src; offset=s-p;
  75.        if (offset>4095 || p<p_src_first || offset==0 || PS || PS || PS)
  76.          {literal: *p_dst++=*p_src++; control>>=1; control_bits++;}
  77.        else
  78.          {PS || PS || PS || PS || PS || PS || PS ||
  79.           PS || PS || PS || PS || PS || PS || s++; len=s-p_src-1;
  80.           *p_dst++=(BYTE) (((offset&0xF00)>>4)+(len-1));
  81.           *p_dst++=(BYTE) (offset&0xFF);
  82.           p_src+=len; control=(control>>1)|0x8000; control_bits++;}
  83. /* end_unrolled_loop: */ if (--unroll) goto begin_unrolled_loop;
  84.     if (control_bits==16)
  85.       {*p_control=control&0xFF; *(p_control+1)=control>>8;
  86.        p_control=p_dst; p_dst+=2; control=control_bits=0;}
  87.    }
  88.  control>>=16-control_bits;
  89.  *p_control++=control&0xFF; *p_control++=control>>8;
  90.  if (p_control==p_dst) p_dst-=2;
  91.  *p_dst_len=p_dst-p_dst_first;
  92.  return;
  93.  overrun: fast_copy(p_src_first,p_dst_first+FLAG_BYTES,(int)src_len);
  94.           *p_dst_first=FLAG_COPY; *p_dst_len=src_len+FLAG_BYTES;
  95. }
  96.  
  97. /////////////////////////////////////////////////////////////////////////////
  98.  
  99. class c4_BoundWriter : public CFile
  100. {
  101.     BYTE *_begin, *_curr, *_end;
  102.     int _base;
  103.     CString _prefix;
  104.     CString _resIncText;
  105.     bool _asText;
  106.     
  107. public:
  108.     c4_BoundWriter (const char* prefix_, bool asText_, int base_)
  109.         : _prefix (prefix_), _asText (asText_), _base (base_)
  110.     {          
  111.         _begin = _curr = new BYTE [c4_BoundStorage::kBlockSize];
  112.         _end = _begin + c4_BoundStorage::kBlockSize;
  113.     }
  114.     
  115.     virtual ~c4_BoundWriter ()
  116.     {   
  117.         FlushNextBlock();
  118.  
  119.         delete [] _begin;
  120.  
  121.         CFile out (_prefix + ".rc", CFile::modeWrite | CFile::modeCreate);
  122.         out.Write((const char*) _resIncText, _resIncText.GetLength());
  123.     }
  124.     
  125.     virtual UINT Read(void* lpBuf, UINT nCount)
  126.     {
  127.         ASSERT(0);
  128.         return 0;
  129.     }
  130.     
  131.     virtual void Write(const void* lpBuf, UINT nCount)
  132.     {
  133.         UINT n = nCount;
  134.  
  135.         while (n > 0)
  136.         {
  137.             if (_curr >= _end)
  138.                 FlushNextBlock();
  139.  
  140.             int k = n;
  141.             if (k > _end - _curr)
  142.                 k = _end - _curr;
  143.  
  144.             memcpy(_curr, lpBuf, k);
  145.  
  146.             _curr += k;
  147.             lpBuf = (const char*) lpBuf + k;
  148.             n -= k;
  149.         }  
  150.     }
  151.  
  152.     void FlushNextBlock()
  153.     {
  154.         if (_curr > _begin)
  155.         {
  156.             DWORD k = _curr - _begin;
  157.             ASSERT(k <= c4_BoundStorage::kBlockSize);
  158.  
  159.             _curr = _begin;
  160.  
  161.             c4_Bytes temp;
  162.             BYTE* tempBuf = temp.SetBuffer((int) k + 256 + FLAG_BYTES);
  163.  
  164.             lzrw1_compress(_begin, k, tempBuf, &k);
  165.             ASSERT((int) k <= temp.Size() - 4);
  166.  
  167.             ASSERT((int) k <= c4_BoundStorage::kBlockSize + FLAG_BYTES);
  168.             ASSERT(*tempBuf <= 1);
  169.  
  170.                 // save the exact stored length and the copy bit
  171.             *(WORD*) tempBuf = ((WORD) k << 1) + *tempBuf; 
  172.  
  173.             ASSERT(c4_BoundStorage::_Encoder);
  174.             c4_BoundStorage::_Encoder(true, _base - 1,
  175.                                             (char*) tempBuf + 2, k - 2);
  176.  
  177.             char num [20];
  178.             wsprintf(num, "%03d", _base);
  179.             CString s = num;
  180.  
  181.             if (_asText)
  182.             {
  183.                 CFile out (_prefix + s + ".rc",
  184.                             CFile::modeWrite | CFile::modeCreate);
  185.  
  186.                 CString line = s + " RCDATA\r\nBEGIN";
  187.  
  188.                 memset(tempBuf + k, 0, 4); // make sure trailing bytes are zero
  189.  
  190.                 for (WORD i = 0; i < k; i += sizeof (DWORD))
  191.                 {
  192.                     if (i % 32 == 0)
  193.                     {
  194.                         out.Write(line, line.GetLength());
  195.                         line = "\r\n  ";
  196.                     }
  197.  
  198.                     wsprintf(num, "0x%08lxL,", *(const DWORD*) (tempBuf + i));
  199.                     
  200.                     line += num;
  201.                 }
  202.  
  203.                 line += "\r\nEND\r\n";
  204.                 out.Write(line, line.GetLength());
  205.  
  206.                 _resIncText += "#include \"" + _prefix + s + ".rc\"\r\n";
  207.             }
  208.             else
  209.             {
  210.                 CFile out (_prefix + s + ".res",
  211.                             CFile::modeWrite | CFile::modeCreate);
  212.  
  213.                 out.Write(tempBuf, k);
  214.  
  215.                 _resIncText += s + " RCDATA \"" + _prefix + s + ".res\"\r\n";
  216.             }
  217.         }
  218.  
  219.         ++_base;
  220.     }
  221. };
  222.  
  223. /////////////////////////////////////////////////////////////////////////////
  224.  
  225. int c4_BoundStorage::DumpAsRes(c4_Storage& orig_, const char* prefix_,
  226.                                     bool asText_, int base_)
  227. {
  228.     c4_BoundWriter writer (prefix_, asText_, base_);
  229.     orig_.SaveToStream(&writer);
  230.     return 0;
  231. }
  232.  
  233. /////////////////////////////////////////////////////////////////////////////
  234.